#ifndef __HUFFMAN
#define __HUFFMAN

#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<iostream>
#include<queue>
#include<string>
#include<fstream>
#include<cmath>
#include<utility>
#include<list>
#include<exception>
#include"io.h"
#include"myVector.h"


namespace Compression
{
	using namespace std;
	using namespace Stream;
	using namespace MyVector;
	template<class T>
	struct huffman
	{
		struct node
		{
			T value;
			int cnt;
			node *son[2];
			node(T v,int c,node *s1,node *s2) : value(v) , cnt(c) { son[0]=s1, son[1]=s2; }
			~node()
			{
				for (int i=0;i<2;++i)
					if (son[i])
						delete son[i];
			}
		};
		struct ptrnodecmp
		{
			bool operator()(const node *p1,const node *p2)
			{
				return p1->cnt>p2->cnt;
			}
		};
		struct huffmanReader
		{
			struct readerNode
			{
				int bitSize,loc;
				readerNode(int bitSize=0,int loc=0) : bitSize(bitSize) , loc(loc) {}
			};
			T *values;
			readerNode *flatTree;
			unsigned size;
			huffmanReader() : values(0) , flatTree(0) {}
			~huffmanReader()
			{
				if (values)
					delete[] values;
				if (flatTree)
					delete[] flatTree;
			}
			static inline int bitReverse(int x,int nsize)
			{
				int n=0;
				for (int i=0;i<nsize;++i)
				{
					n<<=1;
					n|=(x&1);
					x>>=1;
				}
				return n;
			}

			static void createReaderFromTree(const node *act,vector<T> &values,vector<readerNode> &flatTree,int pos=0)
			{
				if (act->son[0]==0)
				{
					flatTree[pos].bitSize=0;
					flatTree[pos].loc=values.size();
					values.push_back(act->value);
					return;
				}
				list<const node*> bfs[2];
				int level=0,foundLeaf=0;
				bfs[level].push_back(act);
				while (!foundLeaf)
				{
					int nextLevel=(level%2+1)%2;
					bfs[nextLevel].clear();
					for (list<const node*>::iterator it=bfs[level%2].begin();it!=bfs[level%2].end();++it)
						if ((*it)->son[0]==0)
						{
							foundLeaf=1;
							break;
						}
						else
						{
							bfs[nextLevel].push_back((*it)->son[0]);
							bfs[nextLevel].push_back((*it)->son[1]);
						}
					if (!foundLeaf)
						++level;
				}
				flatTree[pos].bitSize=level;
				flatTree[pos].loc=flatTree.size();
				flatTree.resize(flatTree.size()+(1<<level));
				level%=2;
				int i=0;
				for (list<const node*>::iterator it=bfs[level].begin();it!=bfs[level].end();++it,++i)
					createReaderFromTree(*it,values,flatTree,flatTree[pos].loc+bitReverse(i,flatTree[pos].bitSize));
			}
			static void saveReader(const char *filename,const node *root)
			{
				vector<T> values;
				vector<readerNode> flatTree(1);
				createReaderFromTree(root,values,flatTree);
				FastOstream readerFile(fopen((string(filename)+".reader").c_str(),"wb"));
				readerFile.writeBinary(flatTree.size(),4);
				for (unsigned i=0;i<flatTree.size();++i)
				{
					readerFile.writeBinary(flatTree[i].bitSize,1);
					readerFile.writeBinary(flatTree[i].loc,3);
				}
				readerFile.writeBinary(values.size(),4);
				for (unsigned i=0;i<values.size();++i)
					readerFile.writeBinary(values[i],sizeof(T));

			}
			void loadReader(const char *filename)
			{
				FastIstream readerFile(fopen((string(filename)+".reader").c_str(),"rb"));
				unsigned valuesSize;
				readerFile.readBinary(size,4);
				flatTree = new readerNode[size];
				for (unsigned i=0;i<size;++i)
				{
					readerFile.readBinary(flatTree[i].bitSize,1);
					readerFile.readBinary(flatTree[i].loc,3);
				}
				readerFile.readBinary(valuesSize,4);
				values = new T[valuesSize];
				for (unsigned i=0;i<valuesSize;++i)
					readerFile.readBinary(values[i],sizeof(T));

			}
			unsigned processBuffer(unsigned &bufferSize,unsigned long long &buffer,T &value) const
			{
				unsigned pos=0,len=0,tmp;
				while (flatTree[pos].bitSize)
				{
					tmp=flatTree[pos].bitSize;
					pos=flatTree[pos].loc+((buffer>>len)&((1<<tmp)-1));
					len+=tmp;
				}
				value=values[flatTree[pos].loc];
				return len;

			}
		};

		vector<bitCode> code;
		node *root;
		huffmanReader reader;
		int size;

		huffman() : root(0) , size(0) {}
		~huffman() 
		{
			if (root)
				delete root;
		}

		//tworzenie tablicy kodu maja dane drzewo, wersja rekurecyjna
		static void gencode(vector<bitCode> &code,node *act,bitCode &s)
		{
			if (act->son[0]==0 && act->son[1]==0)
			{
				if (code.size()<=(unsigned)act->value)
					code.resize(act->value+1);
				code[act->value]=s;
			}
			for (int i=0;i<2;++i)
				if (act->son[i])
				{
					s.push_back(i);
					gencode(code,act->son[i],s);
					s.pop_back();
				}
		}
		
		//liczenie wystapien poszczegolnych kluczy
		//zakladamy, ze klucze sa rzutowalne na inty i nie sa za duze
		//nastepnie robimy drzewo huffmana
		static vector<int> countKeys(const vector<T> &data)
		{
			vector<int> cnt;
			for (unsigned int i=0;i<data.size();++i)
			{
				unsigned int val=(unsigned int)data[i];
				if (cnt.size()<=val)
					cnt.resize(val+1,0);
				++cnt[val];
			}
			return cnt;
		}
		//budowanie drzewa huffmana z danych wystapien
		void buildTree(const vector<int> &cnt)
		{
			priority_queue<node*,vector<node*>,ptrnodecmp> Q;
			for (unsigned int i=0;i<cnt.size();++i)
				if (cnt[i])
				{
					Q.push(new node(i,cnt[i],0,0));
					++size;
				}
			while (Q.size()>1)
			{
				node *n1=Q.top();
				Q.pop();
				node *n2=Q.top();
				Q.pop();
				Q.push(new node(0,n1->cnt+n2->cnt,n1,n2));
			}
			root = Q.top();
		}

		//budujemy kod majac dane drzewo huffmana w root
		void buildCode()
		{
	#ifdef __DEBUG
			if (!root)
				throw std::exception("budowanie kodu: nie zbudowano drzewa");
	#endif
			code.clear();
			gencode(code,root,bitCode());
		}



		inline static void writeProcessBit(char &byte,int &pos,int bit,FastOstream &out)
		{
			if (pos==8)
			{
				out << byte;
				byte=0;
				pos=0;
			}
			byte|=(bit<<(pos++));
		}
	    
		inline static void write(const bitCode &bits,char &byte,int &pos,FastOstream &out)
		{
			if (bits.size()==1)
			{
				writeProcessBit(byte,pos,1,out);
				writeProcessBit(byte,pos,bits.value&1,out);
				return;
			}
			int lo=0;
			while ((unsigned int)(1<<(lo++))<=bits.size())
				writeProcessBit(byte,pos,0,out);
			lo-=2;
			while (lo>=0)
			{
				writeProcessBit(byte,pos,(bits.size()>>lo)&1,out);
				--lo;
			}
			for (unsigned int i=0;i<bits.size();++i)
				writeProcessBit(byte,pos,bits[i],out);
		}
	    
		template<class X>
		inline static void write(const X &val,char &byte,int &pos,FastOstream &out)
		{
			bitCode bits;
			int len=sizeof(X)*8-1;
			while (len>=0 && ((val>>len)&1)==0)
				--len;
			if (len==-1)
				bits.push_back(0);
			while (len>=0)
			{
				bits.push_back((val>>len)&1);
				--len;
			}
			write(bits,byte,pos,out);
		}
	    
		inline static int readGetBit(char &byte,int &pos,FastIstream &in)
		{
			if (pos==8)
			{
				in >> byte;
				pos=0;
			}
			return (byte>>(pos++))&1;
		}
	    
		static void read(bitCode &bits,char &byte,int &pos,FastIstream &in)
		{
			bits.clear();
			int bit=readGetBit(byte,pos,in);
			if (bit==1)
			{
				bits.push_back(readGetBit(byte,pos,in));
				return;
			}
			int len=1;
			while (readGetBit(byte,pos,in)==0)
				++len;
			int size=1;
			while (--len)
			{
				size<<=1;
				size|=readGetBit(byte,pos,in);
			}
			while (size--)
				bits.push_back(readGetBit(byte,pos,in));
		}
		template<class X>
		static void read(X &v,char &byte,int &pos,FastIstream &in)
		{
			bitCode bits;
			read(bits,byte,pos,in);
			memset(&v,0,sizeof(X));
			for (unsigned int i=0;i<bits.size();++i)
				v|=(bits[i]<<(bits.size()-i-1));
		}
	    
	    
		void saveCode(const char *filename)
		{
			char byte=0;
			int pos=0;
			bitCode V;
			FastOstream fout(fopen(filename,"wb"));
			write(size,byte,pos,fout);
			for (unsigned int i=0;i<code.size();++i)
				if (code[i].size()>0)
				{
					write((T)i,byte,pos,fout);
					write(code[i],byte,pos,fout);
				}
			fout << byte;
		}
		void loadCode(const char *filename)
		{
			if (root)
				delete root;
			size=0;
			code.clear();
			FastIstream fin(fopen(filename,"rb"));
			int n;
			char byte;
			int pos=8;
			read(n,byte,pos,fin);
			root = new node(0,0,0,0);
			for (int i=0;i<n;++i)
			{
				bitCode bits;
				T val;
				read(val,byte,pos,fin);
				//printf("%d\n",val);
				read(bits,byte,pos,fin);
				node *act=root;
				for (unsigned int j=0;j<bits.size();++j)
				{
					if (act->son[bits[j]]==0)
						act->son[bits[j]] = new node(0,0,0,0);
					act=act->son[bits[j]];
				}
				act->value = val;       
				if ((unsigned)val>=code.size())
					code.resize(val+1,bitCode());
				if (code[val].size()==0)
				{
					code[val]=bits;
					++size;
				}
			}
		}
		static void encode(const vector<T> &Data,const char *filename)
		{
			FastOstream fout(fopen(filename,"wb"));
			char byte=0;
			int pos=0;
			bitCode V;
			huffman<T> code;
			code.buildTree(countKeys(Data));
			code.buildCode();
			huffmanReader::saveReader(filename,code.root);
			unsigned len=0;
			for (unsigned int i=0;i<Data.size();++i)
				len+=(int)code.code[Data[i]].size();
			//write(len,byte,pos,fout);
			fout.writeBinary(len,4);
			for (unsigned int i=0;i<Data.size();++i)
			{
				bitCode &bits=code.code[Data[i]];
				for (unsigned int j=0;j<bits.size();++j)
					writeProcessBit(byte,pos,bits[j],fout);
			}
			fout << byte;
		}
		static void decode(vector<T> &Data,const char *filename)
		{
			Data.clear();
			FastIstream fin(fopen(filename,"rb"));
			huffmanReader reader;
			reader.loadReader(filename);
			unsigned bitLen,bitDone=0;
			fin.readBinary(bitLen,4);
			unsigned long long bitBuffer=0;
			unsigned bufferSize=0;
			T value;
			while (bitDone<bitLen)
			{
				while (bufferSize<57)
				{
					bitBuffer|=(((unsigned long long)(fin.getc()&255))<<bufferSize);
					bufferSize+=8;
				}
				unsigned read=reader.processBuffer(bufferSize,bitBuffer,value);
				Data.push_back(value);
				bitBuffer>>=read;
				bufferSize-=read;
				bitDone+=read;
			}

	        
		}
		static void saveVector(const vector<T> &vec,const char *filename)
		{
			vector<unsigned char> packed(vec.size()*sizeof(T));
			int bitSize=sizeof(T);
			for (unsigned int i=0;i<vec.size();++i)
				for (int j=0;j<bitSize;++j)
					packed[i*sizeof(T)+j]=(unsigned char)((vec[i]>>(j*8))&255);
			huffman<unsigned char>::encode(packed,filename);
		}
		static vector<T> loadVector(const char *filename)
		{
			vector<unsigned char> packed;
			huffman<unsigned char>::decode(packed,filename);
			int byteSize=sizeof(T);
			vector<T> vec(packed.size()/byteSize);
			for (unsigned i=0;i<vec.size();++i)
			{
				T v=0;
				for (int j=0;j<byteSize;++j)
					v|=(((T)(packed[i*byteSize+j]))<<(j*8));
				vec[i]=v;
			}
			return vec;
		}
		static void decodePostingList(postingList &PL,const huffman<T> &code1,const huffman<T> &code2,FastIstream &file,
			unsigned int bitLen,long long hashValue,int maxCount=1000000000)
		{
			PL.clear();
			T vals[2];
			unsigned long long bitBuffer=0;
			unsigned bufferSize=0,bitDone=0;
			int step=0;
			while (bitDone<bitLen && PL.size()<maxCount)
			{
				while (bufferSize<56)
				{
					/*if (bufferSize<0)
					{
						fprintf(stderr,"blad\n");
						Sleep(10000);
					}*/
					bitBuffer|=(((unsigned long long)(file.getc()&255))<<bufferSize);
					bufferSize+=8;
				}
				if (step==0)
				{
					unsigned read=code1.reader.processBuffer(bufferSize,bitBuffer,vals[0]);
					bitBuffer>>=read;
					bufferSize-=read;
					bitDone+=read;
					++step;
				}
				else
				{
					unsigned read=code2.reader.processBuffer(bufferSize,bitBuffer,vals[1]);
					bitBuffer>>=read;
					bufferSize-=read;
					bitDone+=read;
					PL.push_back(MyVector::PostingItem((int)vals[0],(int)vals[1],hashValue));
					step=0;
				}
			}

		}
	};

}

#endif